package geeksforgeeks.trees;

import geeksforgeeks.trees.TreeTraversals.Node;

public class LowestCommonAncestor {
	public static void main(String[] args) {

		Node root = new Node(20);

		root.left = new Node(8);
		root.left.left = new Node(4);

		root.left.right = new Node(12);
		root.left.right.left = new Node(10);
		root.left.right.right = new Node(14);

		root.right = new Node(22);

		Node lca = findLCA(4, root, 12);
		System.out.println(lca.data);

	}

	public static Node findLCA(int val1, Node root, int val2) {

		// System.out.println(root.data);
		if (root.data > val1 && root.data < val2) {
			return root;
		} 
		if (root.data > val1 && root.data > val2) {
			return findLCA(val1, root.left, val2);
		} else {
			return findLCA(val1, root.right, val2);
		} 
	}
}
